package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import java.util.Arrays;

import com.yahoo.labs.snow.ProblemInstance;
import com.yahoo.labs.snow.Snowflake;

/**
 * Iteratively picks all elements as pivots, starting from the lowest-numbered one. The pickFlake
 * method is modified to pick, at any point, the element that is most similar to any member of the
 * partial bundle.
 * 
 * @author chato
 * 
 */
public class ExhaustiveGreedyAnySimSOBOSolver extends ExhaustiveSOBOSolver {

	public ExhaustiveGreedyAnySimSOBOSolver(ProblemInstance problem) {
		super(problem);
	}

	@Override
	Snowflake pickFlake(final int pivot, IntOpenHashSet clusterMembers) {
		
		int n = clusterMembers.size();
		
		IntOpenHashSet membersSortedSelected = new IntOpenHashSet();
		int[] membersUnsorted = clusterMembers.toArray(new int[] {});
		int[] membersSorted = new int[n];
		Arrays.fill( membersSorted, -1 );

		for (int i = 0; i < n; i++) {
			int mostSimilarElement = -1;
			double mostSimilarElementSimilarity = -1;

			// Choose which element has a larger similarity to any element in the partial bundle
			for (int j = 0; j < n; j++) {
				int elem = membersUnsorted[j];
				if (!membersSortedSelected.contains(elem)) {
					
					// First check if it is closest to the pivot
					if (problem.getCompat(pivot, elem) > mostSimilarElementSimilarity) {
						mostSimilarElement = elem;
						mostSimilarElementSimilarity = problem.getCompat(pivot, elem);
					}
					
					// Then check if it is closest to any element
					for( int k=0; k<i; k++ ) {
						int elem2 = membersSorted[k];
						if (problem.getCompat(elem2, elem) > mostSimilarElementSimilarity) {
							mostSimilarElement = elem;
							mostSimilarElementSimilarity = problem.getCompat(elem2, elem);
						}	
					}
				}
			}
			
			// Add selected element
			if (mostSimilarElement == -1) {
				throw new IllegalStateException("Did not find an element to select");
			}
			membersSortedSelected.add(mostSimilarElement);
			membersSorted[i] = mostSimilarElement;
		}

		return pickFlakeGivenPermutation(pivot, membersSorted);
	}
}
